<html>
<head><meta charset="utf-8"><title>parser output · t-compiler/wg-parselib · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/index.html">t-compiler/wg-parselib</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html">parser output</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="208507862"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/208507862" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Aaron Hill <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#208507862">(Aug 30 2020 at 22:47)</a>:</h4>
<p>Is the plan to include parts of <code>rustc_ast</code> in the parser library, or will it produce some kind of 'more abstract' AST?</p>



<a name="208507912"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/208507912" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Aaron Hill <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#208507912">(Aug 30 2020 at 22:48)</a>:</h4>
<p>Currently, token collection (needed for proc-macros) means that<code>rustc_ast</code> and <code>rustc_parse</code> are fairly tightly coupled</p>



<a name="208507918"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/208507918" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Aaron Hill <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#208507918">(Aug 30 2020 at 22:48)</a>:</h4>
<p>and will be to an even greater extent if <a href="https://github.com/rust-lang/rust/pull/76130">https://github.com/rust-lang/rust/pull/76130</a> is accepted</p>



<a name="208539764"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/208539764" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#208539764">(Aug 31 2020 at 10:12)</a>:</h4>
<p><span class="user-mention" data-user-id="125294">@Aaron Hill</span> there are several end-states we might end up with, and its unclear to me yet which one would be preferable.</p>
<h1>Event-based parsing</h1>
<p>The idea is to completely separate parser and AST, by making parser emit a stream of relatively simple events. The parser is configured with a callback trait which has methods like</p>
<div class="codehilite"><pre><span></span><code><span class="k">trait</span><span class="w"> </span><span class="n">TreeBuilder</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">  </span><span class="k">fn</span> <span class="nf">advance_token</span><span class="p">(</span><span class="o">&amp;</span><span class="k">mut</span><span class="w"> </span><span class="bp">self</span><span class="p">);</span><span class="w"> </span><span class="c1">// all tokens are explicitly advanced, TreeBuilder captures full-fidelity trees</span>
<span class="w">  </span><span class="k">fn</span> <span class="nf">start_node</span><span class="p">(</span><span class="o">&amp;</span><span class="k">mut</span><span class="w"> </span><span class="bp">self</span><span class="p">,</span><span class="w"> </span><span class="n">kind</span>: <span class="nc">NodeKind</span><span class="p">);</span><span class="w"></span>
<span class="w">  </span><span class="k">fn</span> <span class="nf">finish_node</span><span class="p">(</span><span class="o">&amp;</span><span class="k">mut</span><span class="w"> </span><span class="bp">self</span><span class="p">);</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>


<p>rustc would then instantiate a parser with a callback which builds AST and records tokens along the way. rust-analyzer would use a CST-building callback.</p>
<p>Benefits:</p>
<p>* easy to vary parser &amp; ast independently</p>
<p>Drawbacks:</p>
<p>* far from status quo<br>
  * building AST by untyped callback interface seems fundamentally awkward. I want to investigate typed callback interfaces (that's why I made the ungrammar thing).</p>
<p>This approach is used in rust-analyzer internally.</p>
<h1>CST -&gt; AST lowering</h1>
<p>The idea is that the parser just builds a concrete syntax tree (with whitespace &amp; such).<br>
rust-analyzer uses it as is, rustc lowers it to AST.</p>
<p>Benefits:</p>
<p>* simplicity<br>
  * it also pushes us into arguably desirable end-state, where Rustc uses CST instead of AST (current token-recording approaches look like a hacky approximation of CST).</p>
<p>Drawbacks:</p>
<p>* two syntax tree structures in memory<br>
  * CST becomes part of the interface (and, historically, the representation of CST varied a lot in rust-analyzer, and we haven't arrived at the perfect one yet)</p>
<p>This actually was implemented in a proof of concept manner in <a href="https://github.com/rust-lang/rust/pull/70745">https://github.com/rust-lang/rust/pull/70745</a>.</p>
<h1>Brute-forcing the parser to build both CST and AST</h1>
<p>The parser could <em>just</em> build both rust-analyzer's CST and rustc's AST, using a bunch of <code>#[cfg(feature = "ast")]</code> and <code>#[cfg(feature = "cst")]</code>.</p>
<p>Benefits:</p>
<p>* likely the simplest trick to actually pull off<br>
  * might be a stepping stone towards approaches 1 or 2</p>
<p>Drawbacks:</p>
<p>* would requires pretty horrible <code>cfg</code>-ing to shield rust-analyzer from <code>rustc_ast</code><br>
  * doesn't look good from long-term maintenance perspective</p>
<p>This is the approach used by Swift's libsyntax. If we squint hard enough, this is sort of what happens in rustc already as well -- the "record token stream" part roughly corresponds to recording CST.</p>



<a name="209120711"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/209120711" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#209120711">(Sep 04 2020 at 17:31)</a>:</h4>
<p>Realized that there's another option:</p>
<h1>Flat CST -&gt; AST lowering</h1>
<p>Here, parser produces a CST, but a really-really simple one -- just a bunch of ranges packed into a single <code>Vec</code>. I think such simple read-only CST can be much simpler and much faster than what we do in <code>rowan</code>.</p>
<p>This approach can be alternatively seen as the untyped event approach, where we buffer events into a <code>Vec</code>.</p>



<a name="213287329"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/213287329" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#213287329">(Oct 14 2020 at 13:24)</a>:</h4>
<p>Status: I've been distracted with life for the past month, I hope to slowly come back here :)</p>



<a name="216574114"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/216574114" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Aramis Razzaghipour <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#216574114">(Nov 13 2020 at 07:07)</a>:</h4>
<p><span class="user-mention" data-user-id="133169">@matklad</span> You’ve <a href="https://matklad.github.io/2018/06/06/modern-parser-generator.html#parser">mentioned</a>  that using an event-based approach is faster and avoids allocations. I don’t understand; doesn’t adding an event call <code>Vec::push</code>? Also, you mentioned not having to explicitly handle whitespace in the parser due to the event-based architecture. How is this possible?</p>



<a name="216587270"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/216587270" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#216587270">(Nov 13 2020 at 09:38)</a>:</h4>
<p>Adding event does call <code>Vec::push</code> but (pre) allocating vector for events is like one allocation per file.</p>



<a name="216587372"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/216587372" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#216587372">(Nov 13 2020 at 09:39)</a>:</h4>
<blockquote>
<p>Aramis Razzaghipour: @matklad You’ve mentioned that using an event-based approach is faster and avoids allocations. I don’t understand; doesn’t adding an event call Vec::push? Also, you mentioned not having to explicitly handle whitespace in the parser due to the event-based architecture. How is this possible?</p>
</blockquote>
<p>If the parser produces all events for non-whitespace tokens, the caller can reconstruct whitespace-related events without having to remember offsets or full file text</p>



<a name="216587485"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/216587485" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#216587485">(Nov 13 2020 at 09:40)</a>:</h4>
<p>(you can reconstruct whitespace from a syntax tree as well, but you'll need to keep full source text for that, and you'll need to do random access by offsets)</p>



<a name="216606646"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/216606646" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Aramis Razzaghipour <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#216606646">(Nov 13 2020 at 13:01)</a>:</h4>
<p>Ok, I think I understand. Thanks for the help! :)</p>



<a name="231472969"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/231472969" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Steven Trotter <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#231472969">(Mar 23 2021 at 13:49)</a>:</h4>
<p>Newbie question here related to the parser output thread. The above proposals for the parser seem to be about how to get a parser that generates each of the existing AST and CST structures, my (admittedly likely naive) question is, is it an option to try and find another structure that satisfies the criteria for both and adjust rustc/rust_analyzer to this structure? Obviously that means any changes to one have to be supported in the other too but given that rust grammar is (presumably) fairly stable now this maybe this is no bad thing and even a desired outcome of this.</p>
<p>Just wondering if this is something that anyone has thought about, is this a no go before it even gets started because the CST (which I know nothing about) and AST are too different? It would mean a lot of thinking about what that correct structure would be of course and then a lot of work in rustc to make whatever this new thing is generate the HIR again, maybe that's just too much work and too complex for an existing thing.</p>
<p>Also curious if any there are any more thoughts in general about this given that a bit of time has passed since this thread started.</p>
<p>Thanks in advance.</p>



<a name="231473720"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/231473720" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#231473720">(Mar 23 2021 at 13:54)</a>:</h4>
<p>I see it as "<code>rust-analyzer</code> wants a high-fidelity representation of the source code so it can keep comments and whitespace when applying an assist, while <code>rustc</code> wants a simplified one, to not waste memory on comments and other trivia(l) things.".</p>



<a name="231473787"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/231473787" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#231473787">(Mar 23 2021 at 13:55)</a>:</h4>
<p>So you can start with the first and drop the extra info, but that will probably slow down <code>rustc</code>.</p>



<a name="231474164"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/231474164" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#231474164">(Mar 23 2021 at 13:57)</a>:</h4>
<p>yeah, and r-a also wants a representation that works with incremental parsing</p>



<a name="231475615"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/231475615" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Steven Trotter <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#231475615">(Mar 23 2021 at 14:06)</a>:</h4>
<p><span class="user-mention silent" data-user-id="203546">Laurențiu Nicola</span> <a href="#narrow/stream/254930-t-compiler.2Fwg-parselib/topic/parser.20output/near/231473787">said</a>:</p>
<blockquote>
<p>So you can start with the first and drop the extra info, but that will probably slow down <code>rustc</code>.</p>
</blockquote>
<p>Good answer and not entirely unexpected. But then the above <code>CST -&gt; AST lowering</code> would have a similar drawback presumably if you have to generate the CST in the first place? This seems a very good argument against both cases I guess.</p>



<a name="231476223"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/254930-t-compiler/wg-parselib/topic/parser%20output/near/231476223" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/254930-t-compiler/wg-parselib/topic/parser.20output.html#231476223">(Mar 23 2021 at 14:10)</a>:</h4>
<p>It does have "two syntax tree structures in memory" listed as a drawback, even if it doesn't actually call out worse performance. And "build the first one, then drop the extra info" is the CST -&gt; AST approach.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>